package top.ivansong92.example.leetcode.learning.math;


import org.junit.Test;

import java.util.*;

public class TestExample {

    /**
     * Fizz Buzz
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/25/math/60/
     *
     * @param n
     * @return
     */
    public List<String> fizzBuzz(int n) {
        if (n <= 0) {
            return Collections.emptyList();
        }
        List<String> list = new ArrayList<>();

        for (int i = 1; i <= n; i++) {
            boolean tr = (i % 3 == 0);
            boolean fi = (i % 5 == 0);
            if (tr && fi) {
                list.add("FizzBuzz");
                continue;
            }

            if (tr) {
                list.add("Fizz");
                continue;
            }

            if (fi) {
                list.add("Buzz");
                continue;
            }
            list.add(i + "");
        }
        return list;
    }


    public int countPrimes(int n) {
        if (n <= 1) {
            return 0;
        }
        if (n == 2) {
            return 0;
        }
        int[] temp = new int[n - 1];
        temp[0] = 0;
        temp[1] = 1;
        for (int i = 3; i <= n - 1; i++) {
            if (isPrimes(i)) {
                temp[i - 1] = temp[i - 2] + 1;
            } else {
                temp[i - 1] = temp[i - 2];
            }
        }
        return temp[n - 2];
    }

    boolean isPrimes(int n) {
        int k = n / 2;
        for (int i = 2; i <= k; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public int missingNumber(int[] nums) {
        if (nums == null || nums.length < 1) {
            return -1;
        }
        int n = nums.length;
        int k = n * (n + 1) / 2;
        int count = 0;
        for (int nu : nums) {
            count += nu;
        }
        return k - count;

    }


    /**
     * 118. 杨辉三角
     * https://leetcode-cn.com/problems/pascals-triangle/
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        if (numRows < 1) {
            return Collections.emptyList();
        }
        List<List<Integer>> lists = new ArrayList<>();
        for(int i = 1; i <= numRows; i ++) {
            List<Integer> list = new ArrayList<>();
            int last_y = i - 2;
            if (last_y < 0) {
                list.add(1);
                lists.add(list);
                continue;
            }
            List<Integer> list1 = lists.get(last_y);
            for(int j = 0; j < i; j ++) {
                int last_x = j - 1;
                if (last_x < 0 || j >= list1.size()) {
                    list.add(1);
                    continue;
                }
                list.add(list1.get(last_x) + list1.get(j));
            }
            lists.add(list);
        }
        return lists;
    }


    @Test
    public void test2() {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println(minStack.getMin());
    }

    /**
     * 69. Sqrt(x)
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        if (x < 4) {
            return 1;
        }
        int end = x / 2;
        for(int i = end; i > 1; i --) {
            if (i  <= x / i) {
                return i;
            }
        }
        return 1;
    }


    public int mySqrtV2(int x) {
        if (x == 0) {
            return 0;
        }

        if (x < 4) {
            return 1;
        }

        int res = 0;
        int end = x;
        int start = 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;
            if ((long)  mid* mid <= x) {
                res = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return res;
    }


    @Test
    public void testConvertToTitle() {
        System.out.println(convertToTitle(1));
    }

    /**
     * 168. Excel表列名称
     * @param columnNumber
     * @return
     */
    public String convertToTitle(int columnNumber) {
        if (columnNumber <= 0) {
            return "";
        }

        int tmp = columnNumber;
        String res = "";
        while (tmp > 0) {
            tmp --;
            res = (char) (tmp % 26 + 65) + res;
            tmp = tmp/ 26;
        }

        return res;
    }
}


class MinStack {

    /** initialize your data structure here. */
    public MinStack() {

    }

    public void push(int x) {
        Node node = new Node();
        node.val = x;
        node.parent = CURRENT;
        MIN = MIN == null || x < MIN ? x : MIN;
        CURRENT = node;
    }

    public void pop() {
        if (CURRENT == null) {
            return;
        }
        Node node = CURRENT;
        CURRENT = CURRENT.parent;
        node.parent = null;
        if (CURRENT == null) {
            MIN = null;
            return;
        }
        node = CURRENT;
        MIN = node.val;
        while (node != null) {
            int val = node.val;
            if (MIN > val) {
                MIN = val;
            }
            node = node.parent;
        }
    }

    public int top() {
        if (CURRENT == null) {
            throw new RuntimeException("statck  is empty");
        }
        return CURRENT.val;
    }

    public int getMin() {
        if (MIN == null) {
            throw new RuntimeException("statck  is empty");
        }
        return MIN;
    }

    private Integer MIN = null;

    private Node CURRENT = null;

    private static class Node{
        private int val;
        private Node parent;
    }
}